﻿using System;
using System.Diagnostics;

namespace ProjectEuler
{
    internal class Problem15
    {
        public void Solve()
        {
            int size = 20;

            var paths = new long[size + 1,size + 1];

            paths[0, 0] = 0;
            paths[0, 1] = 1;
            paths[1, 0] = 1;
            paths[1, 1] = 2;

            for (int levelIndex = 2; levelIndex <= size; levelIndex++)
            {
                FillLevel(paths, levelIndex);
            }

            Trace.WriteLine("problem 15: " + paths[size, size]);
            Console.WriteLine("problem 15: " + paths[size, size]);
        }

        void FillLevel(long[,] arr, int levelIndex)
        {
            // vertical
            arr[0, levelIndex] = arr[0, levelIndex - 1];
            for (var row = 1; row < levelIndex; row++)
            {
                arr[row, levelIndex] = arr[row - 1, levelIndex] + arr[row, levelIndex - 1];
            }

            // horizontal
            arr[levelIndex, 0] = arr[levelIndex - 1, 0];
            for (var col = 1; col < levelIndex; col++)
            {
                arr[levelIndex, col] = arr[levelIndex - 1, col] + arr[levelIndex, col - 1];
            }

            // corner
            arr[levelIndex, levelIndex] = arr[levelIndex - 1, levelIndex] + arr[levelIndex, levelIndex - 1];
        }

        //public void Solve()
        //{
        //    const int size = 20;

        //    //var powers = new long[size*2];
        //    //InitPowers(ref powers);

        //    //long pathCount = 0;
        //    //var numDigits = (long) (Math.Pow(2, 2 * size) - 1);
        //    //for (long i = 0; i < numDigits; i++)
        //    //{
        //    //    long count = 0;
        //    //    //foreach (var power in powers)
        //    //    //{
        //    //    //    if ((i & power) == power)
        //    //    //    {
        //    //    //        count++;
        //    //    //        if (count > size) break;
        //    //    //    }
        //    //    //}

        //    //    //if (count == size)
        //    //        pathCount++;
        //    //}

        //    //Console.WriteLine("problem 15: " + pathCount);

        //    var arr = new int[size*2];
        //    CountPerms(arr,0);

        //    Console.WriteLine("problem 15: " + permCount);
        //    Trace.WriteLine("problem 15: " + permCount);
        //    Console.WriteLine();
        //}

        //private long permCount = 0;
        //void CountPerms(int[] arr, int startIndex)
        //{
        //    if (startIndex == arr.Length + 1) return;

        //    var countOnes = CountOnes(arr);
        //    if (countOnes == arr.Length / 2)
        //    {
        //        permCount++;
        //        //foreach (var i in arr) { Console.Write(i + " "); }
        //        //Console.WriteLine();
        //        //Console.WriteLine("ok, count={0}", permCount);
        //        return;
        //    }

        //    if (startIndex == arr.Length) return;
        //    arr[startIndex] = 1;
        //    CountPerms(arr, startIndex + 1);
        //    arr[startIndex] = 0;
        //    CountPerms(arr, startIndex + 1);
        //}

        //void Inv(ref int a)
        //{
        //    a = a == 1 ? 0 : 1;
        //}

        //private static void InitPowers(ref long[] powers)
        //{
        //    powers[0] = 1;
        //    for (var i = 0; i < powers.Length; i++)
        //    {
        //        powers[i] = (long) Math.Pow(2, i);
        //    }
        //}

        //int CountOnes(IEnumerable<int> array)
        //{
        //    return array.Where(x => x == 1).Count();
        //}

        //private void Swap(int[] path, int i1, int i2)
        //{
        //    var tmp = path[i1];
        //    path[i1] = path[i2];
        //    path[i2] = tmp;
        //}

        //private void InitPath(ref int[] path)
        //{
        //    for (var i = 0; i < path.Length/2; i++)
        //    {
        //        path[i] = 1;
        //    }
        //}
    }
}